/*
 * @lc app=leetcode.cn id=969 lang=typescript
 *
 * [969] 煎饼排序
 */

// @lc code=start
function pancakeSort(arr: number[]): number[] {
  const n = arr.length;
  const reverse = (arr: number[], idxs: number[], len: number): void => {
    let i = 0;
    let j = len - 1;
    while (i < j) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      [idxs[arr[i]], idxs[arr[j]]] = [i, j];
      i++;
      j--;
    }
  };
  // 保存数字对应的arr下标
  const idxs = new Array(n + 1).fill(-1);
  for (const [idx, num] of arr.entries()) {
    idxs[num] = idx;
  }

  const ans: number[] = [];
  // 遍历每个数字的下标
  for (let i = n; i >= 1; i--) {
    // 如果当前数字已经在合适的位置，这里不用翻转
    if (idxs[i] === i - 1) continue;
    // 先将最大的数字翻转到第一位
    // 如果已经在第一位了，就不用翻转了
    if (idxs[i] + 1 !== 1) {
      // 将反转长度放入答案
      ans.push(idxs[i] + 1);
      reverse(arr, idxs, idxs[i] + 1);
    }
    // 再将最大的数字翻转到最后的位置
    // 如果当前是第一个数字就不用再翻转了
    if (i !== 1) {
      ans.push(i);
      reverse(arr, idxs, i);
    }
  }
  return ans;
}
// @lc code=end
